package map_set.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 复制带随机指针的链表
 * @author zerorain
 * @date 2022/03/18 13:46
 **/
public class Num138 {
        private class Node {
            int val;
            Node next;
            Node random;
            public Node(int val) {
                this.val = val;
                this.next = null;
                this.random = null;
            }
        }
        public Node copyRandomList(Node head) {
            // 边界
            if (head == null) {
                return null;
            }
            // 遍历原链表，构造新链表的节点，存储在Map中
            // Map<原链表结点，新链表结点>
            // 原1 => 新1
            Map<Node,Node> nodeMap = new HashMap<>();
            for (Node x = head;x != null;x = x.next) {
                // 构造新链表的节点
                Node node = new Node(x.val);
                nodeMap.put(x,node);
            }
            // 对新链表进行连接操作
            // 原1.next 和新1.next一一对应
            // 原1.random 和新1.random一一对应
            // 原1.next = 原3  =》新1.next = 新3(这个地址就可以根据原3来取得)
            for (Node x = head;x != null;x = x.next) {
                // 新链表的random和next和原链表一一对应
                // 对于Map来说，Key都是原链表的节点
                // 原1.next = 原3
                nodeMap.get(x).next = nodeMap.get(x.next);
                // 原1.random = 原5
                nodeMap.get(x).random = nodeMap.get(x.random);
            }
            // 返回新链表的头结点，就是原链表的head的映射
            return nodeMap.get(head);
        }
}